#include"sort.h"

void sortprint(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void insertsort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}
void shellsort(int* a, int n)
{
	int gap = n;
	while(gap > 1)
	{
		gap = gap / 2;
		int i = 0;
		for (i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[i + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void selectsort1(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int start = i;
		int min = start;
		while (start < n)
		{
			if (a[start] < a[min])
			{
				min = start;
			}
			start++;
		}
		Swap(&a[i], &a[min]);
	}
}

void selectsort2(int* a, int n)
{
	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int minindex = left;
		int maxindex = left;
		for (int i = left; i <= right; i++)
		{
			if (a[i] < a[minindex])
				minindex = i;
			if (a[i] > a[maxindex])
				maxindex = i;
		}
		Swap(&a[minindex], &a[left]);
		if (left == maxindex)
		{
			maxindex = minindex;
		}
		Swap(&a[maxindex], &a[right]);
		left++;
		right--;
	}
}


void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			Swap(&a[child], &a[child + 1]);
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

void AdjustUp(int* a, int n, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}